// 提交链接 https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/565392995/
// 2616. 最小化数对的最大差值
// 完成日期： 2024.9.17
// 二分搜索 贪心
class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        sort(nums.begin(), nums.end());
        if (!p) return 0;
        int head = 0, tail = nums.back();
        while (head < tail)
        {
            int mid = (head + tail) / 2;
            int n = p;
            for (int i = 0; i < nums.size() - 1; i++)
            {
                if (nums[i + 1] - nums[i] <= mid)
                {
                    i += 1;
                    n -= 1;
                    if (!n) break;
                }
            }
            if (!n) tail = mid;
            else head = mid + 1; 
        }
        return head;
    }
};